package com.leetcode.weekly.contest.no236th;


/**
 * @author 覃国强
 * @date 2021-04-11 11:46
 */
public class A02_找出游戏的获胜者 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int n = 3;
    int k = 1;
    int theWinner = solution.findTheWinner(n, k);
    System.out.println(theWinner);
  }

  static
  class Solution {
    public int findTheWinner(int n, int k) {
      Node head = generateRingList(n);
      Node tail = getListTail(head);
      Node pre = tail;
      while (head.next != head) {
        for (int i = 1; i < k; ++i) {
          pre = head;
          head = head.next;
        }
        pre.next = pre.next.next;
        head = pre.next;
      }
      return head.value;
    }

    private Node getListTail(Node head) {
      Node tail = head;
      while (tail.next != head) {
        tail = tail.next;
      }
      return tail;
    }

    public Node generateRingList(int n) {

      Node head = new Node(0);
      Node tmp = head;

      for (int i = 1; i <= n; ++i) {
        Node cur = new Node(i);
        tmp.next = cur;
        tmp = cur;
      }

      tmp.next = head.next;

      return head.next;
    }


    static class Node {

      int value;

      Node next;

      public Node(int value) {
        this.value = value;
      }
    }
  }

}
